Meng/MSc projects & TA works

The message-passing framework is the foundation of many graph neural networks (GNNs). A typical message-passing framework usually consists of two parts - Transformation (T) and Propagation (P) (ref here and here), respectively responsible for capturing the node attributes information and the structural information. These two sources of information have different roles in different types of graphs (e.g. homogenous/heterogeneous), while in most cases we will not have prior information about which aspect should we focus on. Thus, building a GNN model without a proper design according to graph properties usually cannot achieve satisfactory performance.

This project will use Graph Signal Processing (GSP) to solve this problem. GSP is a powerful toolkit to infer graph structure from the graph signals (i.e. node attributes), and can serve as a method to measure the information from both sides. The first step of this project will be an ablation study on the Transformation and Propagation modules in GNNs, and investigate how they capture the information from node attributes and topological structure. Then we will utilize the techniques in GSP to measure the two sides of information with a novel mechanism. Finally, the ultimate goal is to design new GNNs based on the observations.

Multiple-Users Multi-Arm Bandits (MUMAB) is a special type of bandit problem that widely exists in recommendation systems and ad placements. In this setting, a central agent needs to recommend among M items(arms) to multiple (N) users in a sequential fashion. In many cases, the users are related in some way and this can be represented by a graph that encapsulates important additional information, such as similarities among users in terms of their preferences.

Our previous work develops an algorithm for MUMAB that achieves state-of-the-art results by simply incorporating a graph Laplacian regularizer. This project will continue improving the solution by 1) proposing novel regularizers. 2) tackling the more complicated situation when the graph is constantly changing (i.e. in dynamic graphs).

While most graph machine learning methods have been targeted at static graphs, many important real-world graphs are dynamic -- they change with time. For example, infectious diseases spread along with the changing graph of interpersonal contacts. Graphs of social networks and e-commerce also change as new members join, or new data becomes available.

In the project, we argue that the paradigm of most existing Graph Neural Networks (GNNs), so-called synchronous message passing process (ref here), is not ideal for modeling dynamic graphs. Thus, we then propose to use Asynchronous Message Passing (AMP) models instead to overcome the challenges in dynamic graph machine learning. Different from SMP algorithms, nodes in AMP interact asynchronously by exchanging and reacting to individual messages. The design can potentially identify the redundant information contained in those long-term and long-range messages, and prevent them from propagating through the graph.

Graphs are prominent tools to model relational data in many domains, such as traffic networks, social networks and protein discovery. In many of these applications, the success of algorithms is attributed to recognizing the presence or absence of specific substructures for a specific task, e.g. atomic groups in the case of molecule and protein functions, or cliques in social networks. However, current works based on message-passing networks are spending intensive computation to travel through all possible paths in the graphs by aggregating information from neighbours for every node. Thus, it is natural to think, whether we can avoid this redundant computation but just extract the subgraph instead.

Recent work considers this problem with a new paradigm called agent-based networks, which could directly mine the subgraph in the whole graph and learn the embeddings while walking around the graph. Inspired by this, the project aims to use a similar method to solve multi-task learning or meta-learning on graphs. Specifically, an agent will be designed to walk the graphs with task-specific guidance, so it could be capable to make different decisions while walking on the graph. The difficulty lies in how to design the strategy of walking and how can the agent efficiently extract the information from the graphs. (E.g. Goal-conditioned RL methods could be considered)

Multimodal learning is a technique aiming to combine information from different resources, and is gaining more popularity in the field of image-text translation recently thanks to the giant success of large cross-modal pretrained models like CLIP, DALL-e. With this inspiration, it is natural to wonder if we can do a similar job in the community of graphs.

This project will first consider a novel cross-modal task - the translation between graphs and Natural Language. We will start with generating molecule descriptions based on molecule graphs as the dataset can be easily retrieved. And the next step could be generating graphs from description tasks, which is a much more complicated task. Finally, we will build a large pre-trained model cross the modalities between graphs and natural language to achieve better knowledge representation and better performance on several downstream tasks, like property prediction, drug discovery or protein design.

Graph Neural Networks (GNNs) have shown their competency in encoding graph-structured data. However, the explainability of GNNs is not always coherent with the model, and most of the existing models gain explainability instance-wise - they provide input-dependent explanations for each input graph. This project aims to construct a novel type of graph neural networks that can gain model-level explainability and expressiveness by combing Contextual Stochastic Block Models (CSBM) and slot attention networks into GNNs.

Contextual Stochastic Block Model (CSBM) (also see here)is a widely used tool in the research of graph theories with applications like spectral clustering and community detection. CSBM assumes that each node $\mathcal{V}_i$ in graph $\mathcal{G}$ belongs to a block (i.e. community) $\mathbf{B}_j$, and the blocks are internally connected to each other. The idea is to use a framework similar to CSBM to construct graph neural networks to gain explainability and expressiveness by iteratively refining the graph information using CSBM. The difficult part would be how to incorporate community discovery into GNNs. A method could be using slot attention networks or capsule networks, but there are always other possible solutions.